package com.bleem.ds.xinshou.a03;

/**
 * @author SuYanchun
 * @since 2024-08-16 16:12
 */
public class BinarySearch {

    /**
     * 二分查找法
     *
     * @param arr    数组
     * @param target 查找目标值
     * @return 目标值索引
     */
    public static Integer binarySearch(int[] arr, Integer target) {
        int index = -1;

        if (null == arr || arr.length == 0) {
            return index;
        }
        int start = 0;
        int end = arr.length - 1;

        while (start <= end) {
            int targetIndex = start + end >>> 1;
            if (arr[targetIndex] == target) {
                return targetIndex;
            } else if (arr[targetIndex] < target) {
                start = targetIndex + 1;
            } else {
                end = targetIndex - 1;
            }
        }
        return index;
    }


    /**
     * 在有序数组中找到 大于等于 num 最左的位置
     * @param arr 有序数组
     * @param target 目标值
     * @return 大于等于目标值最左索引
     */
    public static int mostLeft(int[] arr, int target) {
        int index = -1;
        if (null == arr || arr.length == 0) {
            return index;
        }
        int start = 0;
        int end = arr.length - 1;


        while (start <= end) {
            int targetIndex = start + end >>> 1;
            if (arr[targetIndex] >= target) {
                index = targetIndex;
                end = targetIndex  -1;
            } else {
                start = targetIndex + 1;
            }
        }
        return index;
    }


    public static int mostLeft1(int[] arr, int target) {
        int index = -1;
        if (null == arr || arr.length == 0) {
            return index;
        }
        int start = 0;
        int end = arr.length - 1;

        while (start <= end) {
            int targetIndex = start + end >>> 1;
            if (arr[targetIndex] == target){
                index = targetIndex;
                end = targetIndex  -1;
            } else if (arr[targetIndex] >= target) {
                end = targetIndex  -1;
            } else {
                start = targetIndex + 1;
            }
        }
        return index;
    }


    /**
     * 在有序数组中找到 小于等于 num 最右的位置
     * @param arr 有序数组
     * @param target 目标值
     * @return 大于等于目标值最左索引
     */
    public static int mostRight(int[] arr, int target) {
        int index = -1;
        if (null == arr || arr.length == 0) {
            return index;
        }
        int start = 0;
        int end = arr.length - 1;


        while (start <= end) {
            int targetIndex = start + end >>> 1;
            if (arr[targetIndex] <= target) {
                index = targetIndex;
                start = targetIndex + 1;
            } else {
                end = targetIndex  -1;
            }
        }
        return index;
    }

}
